The present invention relates to a method and apparatus for reducing the error rate of received data, and, more particularly, is directed to Viterbi decoding of encoded data.
The Viterbi algorithm is used to estimate the values of a sequence of received information. The information values may be chosen from a binary set, such as (0, 1), and sampled at discrete times. Typically, the information sequence is transmitted through a channel which adds memoryless noise thereto. At a receiver, the original sequence of information is extracted from the received information, as corrupted by noise introduced by the transmission channel.
A version of the Viterbi decoding algorithm, referred to herein as Ferguson's technique, has been proposed in M. J. Ferguson, "Optimal reception for binary partial response channels", Bell System Technical Journal, Vol. 51, No 2, pages 493-505, February 1972, the disclosure of which is incorporated by reference herein.
Ferguson explains that a partial response signalling scheme is useful as it eliminates the need for ideal boxcar filters. Since not all code sequences are possible when using a partial response signalling scheme, it is appropriate to consider the received sequence as a trellis of binary points, and determine the trellis path of maximum likelihood. At each point in time, there are two maximum likelihood paths respectively leading up to one of the two possible present values. One of these maximum likelihood paths must be the optimal path. As explained at page 499 of Ferguson, the state of the received code sequence is classified as being one of a plus (+) merge state, minus (-) merge state, and no merge state depending on its trellis pattern. The code sequence is decoded, that is, its values are determined, in accordance with the state at that time and at neighboring times.
More particularly, in Ferguson's technique, only when both the type of the preceding or most recent merge, that is, a (+) or (-) merge, and the type ((+) or (-)) of the present merge are known is it possible to decode with certainty the code sequence points between the most recent merge and the present merge. That is, decoding cannot occur with certainty when the present state is a no merge state.
Hitherto, when the no merge state has continued or persisted for multiple times, the value of the original code sequence has been estimated and stored in a buffer, and when the next plus (+) merge or minus (-) merge occurs, the values in the buffer have been updated, if necessary, and output as the recovered code sequence.
However, when the no merge state continues for a sufficiently long period of time, the number of estimated code values exceeds the capacity or size of the buffer. The oldest estimated values are then typically output as recovered data. When the next (+) or (-) merge occurs, the estimated values still in the buffer can be corrected, if necessary, but it is impossible to correct the values which have been output as recovered code values. Therefore, an error occurs in the recovered code sequence.
Additionally, in this situation, Ferguson's technique is defined such that an additional error occurs in the recovered code sequence when the stored estimated values are corrected after occurrence of a (+) or (-) merge state. Therefore, as explained at page 502 of Ferguson, a total of two errors may occur in the recovered code sequence when the reception buffer overflows.